package org.example.myleet.p761;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * 以下解析是参考官方解题思路
 */
public class Solution {
    public String makeLargestSpecial(String s) {
        return sort(s);
    }

    private String sort(String s) {
        if (s.length() < 1) {
            return s;
        }
        String sub = s.substring(1, s.length() - 1);
        if (isSpecial(sub)) {
            //如果s的头尾去掉之后如果可以排序，则也进行排序
            sub = sort(sub);
            s = s.charAt(0) + sub + s.substring(s.length() - 1);
        }
        //将s按照1和0互补的情况进行切割
        List<String> specialParts = new ArrayList<>();
        StringBuilder part = new StringBuilder();
        int level = 0;
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            part.append(c);
            if (c == '1') {
                ++level;
            } else {
                --level;
            }
            if (level == 0 && part.length() < s.length()) {
                String p = part.toString();
                p = sort(p);
                specialParts.add(p);
                part = new StringBuilder();
            }
        }
        if (part.length() > 0 && part.length() < s.length()) {
            String p = part.toString();
            p = sort(p);
            specialParts.add(p);
        }
        //最后将这些部分进行按字典序倒序的方式排列，完成排序
        specialParts.sort(Comparator.reverseOrder());
        if (specialParts.size() > 0) {
            return String.join("", specialParts);
        }
        return s;
    }

    private boolean isSpecial(String s) {
        if ((s.length() & 1) == 1) {
            return false;
        }
        if (s.startsWith("0") || !s.endsWith("0")) {
            return false;
        }
        int level = 0;
        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) == '1') {
                ++level;
            } else {
                --level;
            }
            if (level < 0) {
                return false;
            }
        }
        return level == 0;
    }
}
